# coding=utf-8
__author__ = 'st316'
'''
Given a string, find the length of the longest substring without repeating characters.
For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3.
For "bbbbb" the longest substring is "b", with the length of 1.
注意：
两个指针 一个开头一个结尾，每次遇见重复时候把开头到重复字符这个子串种所有字符的标志位的重置
则重复字符的下一个开始到结尾字符无重复，继续扫描，直至结束
两个指针都最多移动N步，时间复杂度为O（N）
'''


class Solution:
    # @return an integer,O(N)
    def lengthOfLongestSubstring(self, s):
        n = len(s)
        i = 0  # 开始
        j = 0  # 结尾
        maxLen = 0
        exist = [False for x in xrange(256)]
        while j < n:
            if exist[ord(s[j])]:
                maxLen = max(maxLen, j - i)
                while s[i] != s[j]:  # 从开始到上一个重复字符之间的字符标志位重置为false
                    exist[ord(s[i])] = False
                    i += 1
                i += 1
                j += 1
            else:
                exist[ord(s[j])] = True
                j += 1
        maxLen = max(maxLen, n - i)
        return maxLen

    # @return an integer,O(N*N)
    def lengthOfLongestSubstringX(self, s):
        start = 0
        end = len(s) - 1
        m = 0
        while start <= end and end - start + 1 > m:
            start, tm = self.findM(s, start)  # 从上一个重复字符的下一位找起
            # print start, tm, s[start - tm:start]
            if tm > m:
                m = tm
        return m

    def findM(self, s, start):  # 找到s中从start位置开始的最长不重复字串
        appeared = {}
        cur = start
        m = 1
        appeared[s[cur]] = cur
        cur += 1
        for c in s[start + 1:]:
            if c in appeared:
                return appeared[s[cur]] + 1, m
            else:
                appeared[c] = cur
                cur += 1
                m += 1
        return cur, m


if __name__ == '__main__':
    s = Solution()
    import time

    ct = time.time()
    print s.lengthOfLongestSubstring('ddddddddddddddddddddddddddddddddddddddddddddddddddddddd'*5000)
    st = time.time()
    print s.lengthOfLongestSubstringX('ddddddddddddddddddddddddddddddddddddddddddddddddddddddd'*5000)
    et = time.time()
    print et
    print st - ct, et - st

